# 有 n 个网络节点，标记为 1 到 n。
#
#  给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，
#  其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
#
#  现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
#
#  示例 1：
# 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
# 输出：2
#
#  示例 2：
# 输入：times = [[1,2,1]], n = 2, k = 1
# 输出：1
#
#  示例 3：
# 输入：times = [[1,2,1]], n = 2, k = 2
# 输出：-1
import collections
import heapq
from typing import List


class Solution:
    def networkDelayTime6(self, times: List[List[int]], n: int, k: int) -> int:
        """
        SPFA算法
        是Bellman-Ford的一种提升算法（队列优化进行松弛）
        :param times:
        :param n:
        :param k:
        :return:
        """
        adjList = self.getAdjList(times)
        needMinTimes = [float('inf')] * (n + 1)  # 表示从开始节点(k节点)到 i 所需的最短时间  needTimes[i] = inf 代表 k 节点不可达 i
        needMinTimes[k] = 0
        q = collections.deque()
        q.append(k)
        while q:
            node = q.popleft()
            if neighbours := adjList.get(node):
                for v, w in neighbours:
                    if needMinTimes[node] + w < needMinTimes[v]:
                        needMinTimes[v] = needMinTimes[node] + w
                        q.append(v)
        res = max(needMinTimes[1:])
        return res if res < float('inf') else -1

    def networkDelayTime5(self, times: List[List[int]], n: int, k: int) -> int:
        """
        Bellman-Ford算法
        支持存在负权
        :param times:
        :param n:
        :param k:
        :return:
        """
        needMinTimes = [float('inf')] * (n + 1)  # 表示从开始节点(k节点)到 i 所需的最短时间  needTimes[i] = inf 代表 k 节点不可达 i
        needMinTimes[k] = 0
        for _ in range(n - 1):  # 最多松弛n - 1次达到最优
            # times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
            for u, v, time in times:
                if needMinTimes[u] + time < needMinTimes[v]:
                    needMinTimes[v] = needMinTimes[u] + time

        res = max(needMinTimes[1:])
        return res if res < float('inf') else -1

    def networkDelayTime4(self, times: List[List[int]], n: int, k: int) -> int:
        """
        Floyd算法（得到从任意起点出发，到达任意起点的最短距离）
        基于「贪心」、「动态规划」求一个图中 所有点到所有点 最短路径的算法，可以处理负权边，但是不能处理负权回路的情况
        思想：以每个点为「中转站」，刷新所有「入度」和「出度」的距离
        :param times:
        :param n:
        :param k:
        :return:
        """
        adjMatrix = self.getAdjMatrix(times, n)
        for i in range(n):
            adjMatrix[i][i] = 0
        for mid in range(n):
            for i in range(n):
                for j in range(n):
                    adjMatrix[i][j] = min(adjMatrix[i][j], adjMatrix[i][mid] + adjMatrix[mid][j])
        res = max(adjMatrix[k - 1])
        return res if res < float('inf') else -1

    def networkDelayTime3(self, times: List[List[int]], n: int, k: int) -> int:
        """
        Dijkstra算法(贪心 + BFS)，该算法无法处理存在负权的图
        将节点分为两类：已确定从起点到该点的最短路长度的节点(已确定节点)，以及未确定从起点到该点的最短路长度的节点（未确定节点)
        每次从 未确定节点 中取一个与起点距离最短的点，将它归类为 已确定节点 ，并用它更新从起点到其他所有 未确定节点 的距离。(每次确定到达一个点所需的最小时间)
        直到所有点都被归类为 已确定节点。
        :param times:
        :param n:
        :param k:
        :return:
        """
        def dijkstra1() -> int:  # 朴素的Dijkstra算法，更适合于稠密图(边数远大于点数)
            adjMatrix = self.getAdjMatrix(times, n)
            needMinTimes = [float('inf')] * n  # 表示从开始节点(k节点)到 i 所需的最短时间  needTimes[i] = inf 代表 k 节点不可达 i
            needMinTimes[k - 1] = 0
            confirmed = [False] * n  # 是否已经确定了到达的最短时间
            for _ in range(n):  # 循环 n 次,每次确定到达一个点所需的最小时间
                # 每次找到 最短距离最小 且 未被更新 的点 t
                t = -1
                for i in range(n):  # 寻找当前能够到达的所需时间最小的点
                    if not confirmed[i] and (t == -1 or needMinTimes[i] < needMinTimes[t]):
                        t = i
                confirmed[t] = True
                for j, time in enumerate(adjMatrix[t]):  # 更新
                    needMinTimes[j] = min(needMinTimes[j], needMinTimes[t] + time)
            res = max(needMinTimes)
            return res if res < float('inf') else -1

        def dijkstra2() -> int:  # 使用堆优化的Dijkstra算法
            adjList = self.getAdjList(times)
            needMinTimes = [float('inf')] * (n + 1)  # 表示从开始节点(k节点)到 i 所需的最短时间  needTimes[i] = inf 代表 k 节点不可达 i
            heap = [(0, k)]  # 小根堆中存放 (收到信号时间，结点)
            while heap:
                t, tmpNode = heapq.heappop(heap)
                if needMinTimes[tmpNode] < t:
                    continue
                needMinTimes[k] = t
                for u, time in adjList[tmpNode]:
                    if (tmp := needMinTimes[tmpNode] + time) < needMinTimes[u]:
                        needMinTimes[u] = tmp
                        heapq.heappush(heap, (tmp, u))
            res = max(needMinTimes[1:])
            return res if res < float('inf') else -1
        return dijkstra2()

    def networkDelayTime2(self, times: List[List[int]], n: int, k: int) -> int:
        """
        BFS(涉及最大最小的问题 BFS 显然比 DFS 更合适)
        求出节点 k 到其余所有点的最短路，其中的最大值就是答案。若存在从 k 出发无法到达的点，则返回 −1
        :param times:
        :param n:
        :param k:
        :return:
        """
        adjList = self.getAdjList(times)
        # needTimes[i] = m 表示从开始节点(k节点)到 i 所需的最短时间  needTimes[i] = -1 代表 k 节点不可达 i
        needMinTimes = [-1] * (n + 1)
        q = collections.deque()
        q.append((k, 0))  # 队列中存放 (结点，该节点收到K发来信号的最短时间)
        needMinTimes[k] = 0
        while q:
            tmpNode, totalTime = q.popleft()
            for neighbour, time in adjList[tmpNode]:
                tmpTotal = totalTime + time
                # 仅当结点未收到或收到时间比记录时间更早才更新并入队
                if needMinTimes[neighbour] == -1 or tmpTotal < needMinTimes[neighbour]:
                    needMinTimes[neighbour] = tmpTotal
                    q.append((neighbour, tmpTotal))
        return max(needMinTimes) if -1 not in needMinTimes[1:] else -1

    def networkDelayTime1(self, times: List[List[int]], n: int, k: int) -> int:
        """
        求出节点 k 到其余所有点的最短路，其中的最大值就是答案。若存在从 k 出发无法到达的点，则返回 −1
        DFS(对于求最短路并不合适)
        简单递归的搜索一遍图，
        当然继续向下搜索的前提是遍历到某一结点的时间有减少，不然没必要继续向下继续搜索了，(进行了剪枝也就不可能出现遍历环，因此不需要记已经遍历过的元素)
        :param times:
        :param n:
        :param k:
        :return:
        """
        adjList = self.getAdjList(times)
        # needTimes[i] = m 表示从开始节点(k节点)到 i 所需的最短时间  needTimes[i] = -1 代表 k 节点不可达 i
        needMinTimes = [-1] * (n + 1)

        def dfs(i: int, time: int) -> None:  # 在 time 时间能到达 i 结点
            if needMinTimes[i] == -1 or time < needMinTimes[i]:
                needMinTimes[i] = time
                for neighbour, t in adjList[i]:
                    dfs(neighbour, time + t)

        dfs(k, 0)
        return max(needMinTimes) if -1 not in needMinTimes[1:] else -1

    def getAdjList(self, times: List[List[int]]) -> dict:
        adjList = collections.defaultdict(set)
        for u, v, distance in times:
            adjList[u].add((v, distance))
        return adjList

    def getAdjMatrix(self, times: List[List[int]], n: int) -> List[List[int]]:
        adjMatrix = [[float('inf')] * n for _ in range(n)]
        for u, v, w in times:
            adjMatrix[u - 1][v - 1] = w
        return adjMatrix

    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        return self.networkDelayTime6(times, n, k)


if __name__ == "__main__":
    times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
    n, k = 4, 2
    # times = [[1, 2, 1]]
    # n, k = 2, 1
    # times = [[1, 2, 1], [2, 1, 3]]
    # n = k = 2
    # times = [[1, 2, 1], [2, 3, 2], [1, 3, 2]]
    # n, k = 3, 1
    print(Solution().networkDelayTime(times, n, k))
